/*
 * @lc app=leetcode.cn id=47 lang=typescript
 *
 * [47] 全排列 II
 *
 * https://leetcode.cn/problems/permutations-ii/description/
 *
 * algorithms
 * Medium (65.79%)
 * Likes:    1578
 * Dislikes: 0
 * Total Accepted:    562.6K
 * Total Submissions: 855.1K
 * Testcase Example:  '[1,1,2]'
 *
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * ⁠[1,2,1],
 * ⁠[2,1,1]]
 *
 *
 * 示例 2：
 *
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 *
 *
 */

// @lc code=start
function permuteUnique(nums: number[]): number[][] {
  let res: number[][] = [];
  let sortedNums = nums.sort((a, b) => a - b);
  let visit = {};

  function helper(idx, path) {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }

    for (let i = 0; i < sortedNums.length; i++) {
      if (visit[i] === true) {
        continue;
      }

      if (
        sortedNums[i] === sortedNums[i - 1] &&
        i > 0 &&
        visit[i - 1] === true
      ) {
        continue;
      }

      visit[i] = true;
      path.push(sortedNums[i]);

      helper(i + 1, path);

      visit[i] = false;
      path.pop();
    }
  }

  helper(0, []);

  return res;
}

permuteUnique([1, 2, 3]);

// @lc code=end
